
// 时间复杂度：O(n*logn)
// 空间复杂度：O(1)

const { LinkedList, ListNode } = require('../1. 链表基础/1. 建立线性链表')

function mergeSort(head) {
    // 1. 分割环节
    if (!head || !head.next) { 
        return head
    }
    // 快慢指针找到中心节点
    let slow = head
    let fast = head.next

    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }

    let leftHead = head
    let rightHead = slow.next
    slow.next = null
    return merge(mergeSort(leftHead), mergeSort(rightHead))

}

function merge(left, right) {
    // 2. 归并环节
    let dummyHead = new ListNode(-1)
    let cur = dummyHead
    while (left && right) {
        if (left.val <= right.val) {
            cur.next = left
            left = left.next
        } else {
            cur.next = right
            right = right.next
        }
        cur = cur.next
    }
    if (left) {
        cur.next = left
    } else {
        cur.next = right
    }
    return dummyHead.next
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
console.log(mergeSort(linkList.head))